{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #报数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #报数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实现一个十进制数字报数程序，请按照数字从小到大的顺序返回一个整数数列，该数列从数字 <code>1</code> 开始，到最大的正整数 <code>cnt</code> 位数字结束。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cnt = 2\n",
    "<strong>输出：</strong>[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [da-yin-cong-1dao-zui-da-de-nwei-shu-lcof](https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [da-yin-cong-1dao-zui-da-de-nwei-shu-lcof](https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [i for i in range(1,10**cnt)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10 ** cnt):\n",
    "            res.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1,10**cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10 ** cnt):\n",
    "            res.append(i)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        ans = []\n",
    "        n = 1\n",
    "        print(10**cnt)\n",
    "        while(n!=10**cnt):\n",
    "            ans.append(n)\n",
    "            n+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1, 10 ** cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        n = 0\n",
    "        for _ in range(cnt):\n",
    "            n *= 10\n",
    "            n += 9\n",
    "        return [i for i in range(1, n + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        i = 1\n",
    "        while i<= (10 ** cnt) - 1 :\n",
    "            ans.append(i)\n",
    "            i += 1\n",
    "\n",
    "        return  ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1, 10**cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        i = 1\n",
    "        while i < 10**cnt:\n",
    "            res.append(i)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        output = []\n",
    "        for i in range(1, 10 ** cnt):\n",
    "            output += [i]\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        i = 1\n",
    "        while i < 10**cnt:\n",
    "            res.append(i)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [x for x in range(1,pow(10,cnt))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        ans = [i for i in range(1, 10 ** cnt)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        if cnt<1:\n",
    "            return []\n",
    "        num=1\n",
    "        for _ in range(cnt):\n",
    "            num*=10\n",
    "        return [i for i in range(1,num)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        maximum = 10 ** cnt\n",
    "        return list(range(1, maximum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        if cnt == 0:\n",
    "            return []\n",
    "        ans = []\n",
    "        for i in range(1, 10**cnt):\n",
    "            ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1,10**cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        i, res = 1, []\n",
    "        while len(str(i))<=cnt:\n",
    "            res.append(i)\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, n: int) -> List[int]:\n",
    "        num = 1\n",
    "        for i in range(n):\n",
    "            num *= 10\n",
    "        ans = [] \n",
    "        for i in range (1,num):\n",
    "            ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10 ** cnt):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [i for i in range(1, 10**cnt)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        maxNumber = pow(10, cnt)\n",
    "        ans = []\n",
    "        for i in range(1, maxNumber):\n",
    "            ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [i for i in range(1,10**cnt)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        # res = []\n",
    "        # for i in range(1, 10**cnt):\n",
    "        #     res.append(i)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        return [i for i in range(1, 10**cnt)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res=[]\n",
    "        for i in range(1,10**cnt):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        cnt = 10**cnt\n",
    "        l = []\n",
    "        if cnt == 0:\n",
    "            return l\n",
    "        else:\n",
    "            for i in range(1,cnt):\n",
    "                if i < cnt:\n",
    "                    l.append(i)\n",
    "            return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res=[]\n",
    "        for i in range(1,10**cnt):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10 ** cnt):\n",
    "            res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1, 10**cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1, int(10 ** cnt)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1,10**cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [i for i in range(1,10**(cnt))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10**cnt):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        end=10**cnt\n",
    "        ans=list(range(1,end))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        if cnt<1:\n",
    "            return []\n",
    "        num=1\n",
    "        for _ in range(cnt):\n",
    "            num*=10\n",
    "        res=[]\n",
    "        for i in range(1,num):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        maxNum = 1\n",
    "        for i in range(cnt):\n",
    "            maxNum *= 10\n",
    "\n",
    "        # 最大值是 maxNum - 1\n",
    "        res = list(range(1, maxNum))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [i for i in range(1, pow(10, cnt))]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        i = 1\n",
    "        while i < 10 ** cnt:\n",
    "            res.append(i)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        times = 10 ** cnt\n",
    "        ret = []\n",
    "        for i in range(times - 1):\n",
    "            num = i + 1\n",
    "            ret.append(num)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(1, 10 ** cnt):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        up = int(''.join(['9'] * cnt))\n",
    "        return list(range(1, up+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return [i for i in range(1, pow(10, cnt))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        def dfs(digit_idx):\n",
    "            if digit_idx == cnt:\n",
    "                if num[self.start:] != [\"0\"]:\n",
    "                    res.append(int(\"\".join(num[self.start:])))\n",
    "                if self.num_9 + self.start == cnt:\n",
    "                    self.start -= 1\n",
    "                return\n",
    "\n",
    "            for i in range(10):\n",
    "                if i == 9:\n",
    "                    self.num_9 += 1\n",
    "                num[digit_idx] = str(i)\n",
    "                dfs(digit_idx + 1)\n",
    "            self.num_9 -= 1\n",
    "\n",
    "        self.start, self.num_9 = cnt - 1, 0\n",
    "        res, num = [], [0] * cnt\n",
    "\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        #法1 先求出最大数 再直接打印\n",
    "        \"\"\"\n",
    "        i = 1\n",
    "        maxnum = 0\n",
    "        for j in range(cnt):\n",
    "            maxnum = maxnum * 10 + 9\n",
    "        \n",
    "        ans = []\n",
    "        for j in range(1,maxnum+1):\n",
    "            ans.append(j)\n",
    "        \n",
    "        return ans\n",
    "        \"\"\"\n",
    "        #简化版代码\n",
    "        return list(range(1, 10**cnt))\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        if not cnt:return []\n",
    "        res = []\n",
    "        for i in range(1,10**cnt):\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        def helper(x):\n",
    "            if x==cnt:\n",
    "                s=''.join(num[self.start:])\n",
    "                if s!='0':\n",
    "                    res.append(int(s))\n",
    "                if cnt-self.start==self.nine:\n",
    "                    self.start-=1\n",
    "                return \n",
    "            for i in range(10):\n",
    "                if i==9:\n",
    "                    self.nine+=1\n",
    "                num[x]=str(i)\n",
    "                helper(x+1)\n",
    "            self.nine-=1\n",
    "        num=['0']*cnt \n",
    "        res=[]\n",
    "        self.start=cnt-1\n",
    "        self.nine=0\n",
    "        helper(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(1, 10**cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        nums=[0]*(cnt+1)\n",
    "        def pprint(nums):\n",
    "            x=0\n",
    "            i=len(nums)-1\n",
    "            while nums[i]==0:\n",
    "                i-=1\n",
    "            for j in range(i,-1,-1):\n",
    "                x= x*10+nums[j]\n",
    "            return x\n",
    "        \n",
    "        ans=[]\n",
    "        i=0\n",
    "        nums[0]=1\n",
    "        while i!=cnt:\n",
    "            ans.append(pprint(nums))\n",
    "            i=0\n",
    "            while nums[i]==9:\n",
    "                nums[i]=0\n",
    "                i+=1\n",
    "            nums[i]+=1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> [int]:\n",
    "        def dfs(x):\n",
    "            if x == cnt:\n",
    "                s = ''.join(num[self.start:])\n",
    "                if s != '0': res.append(int(s))\n",
    "                if cnt - self.start == self.nine: self.start -= 1\n",
    "                return\n",
    "            for i in range(10):\n",
    "                if i == 9: self.nine += 1\n",
    "                num[x] = str(i)\n",
    "                dfs(x + 1)\n",
    "            self.nine -= 1\n",
    "        \n",
    "        num, res = ['0'] * cnt, []\n",
    "        self.nine = 0\n",
    "        self.start = cnt - 1\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "\n",
    "        # 生成长度为len的数字，正在确定第 x 位\n",
    "        def recur(x : int, len: int):\n",
    "            # 当前数字 cur 满足长度，则压入 res\n",
    "            if x == len:\n",
    "                res.append(int(\"\".join(cur)))\n",
    "                return \n",
    "            # X = 0 表示当前处理左边第一位数字，此位不能为 0，因此本次循环从 1 开始\n",
    "            start = 1 if x == 0 else 0\n",
    "            for i in range(start, 10):\n",
    "                # 确定当前位 x 上的数字\n",
    "                cur.append(str(i))\n",
    "                # 继续递归第 x + 1 位\n",
    "                recur(x + 1, len)\n",
    "                # 回溯时，弹出当前位 x 上的数字，在下一次循环中重新确定当前位 x 上的数字\n",
    "                cur.pop()\n",
    "        \n",
    "        res = []\n",
    "        cur = []\n",
    "        # 每次生成长度为 i 的一组数字，每次都用第一位，即 x = 0 开始\n",
    "        for i in range(1, cnt + 1):\n",
    "            recur(0, i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        queue = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "        res = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]\n",
    "        result=[]\n",
    "        for i in range(1, cnt):\n",
    "            tmp_res = []\n",
    "            for x in res[i - 1]:\n",
    "                for y in queue:\n",
    "                    tmp_res.append(x * 10 + y)\n",
    "            res.append(tmp_res)\n",
    "        for value in res:\n",
    "            result.extend(value)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> list[int]:\n",
    "        end = int(''.join(['9' for v in range(cnt)]))+1\n",
    "        return list(range(end))[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(pow(10,cnt)):\n",
    "            ans.append(i)\n",
    "        return ans[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        a = '1'\n",
    "        for i in range(cnt):\n",
    "            a = a +'0'\n",
    "        ans = [i for i in range(int(a))]\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNumbers(self, cnt: int) -> List[int]:\n",
    "        return list(range(10**cnt))[1:]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
